package org.reborn.engine.model

import org.reborn.engine.model.mesh.Mesh
import org.reborn.math._

import org.reborn.model.bound._

import scala.collection.mutable.ArrayBuffer

import AxisPosition._

class OctTree(val minExtents:VectorF, val maxExtents:VectorF) {
  require(minExtents.length == 3)
  require(maxExtents.length == 3)
  
  type OctNodeLoc = (AxisPosition.AxisPosition,AxisPosition.AxisPosition,AxisPosition.AxisPosition)
	
  val center = ((maxExtents - minExtents) * .5f) + minExtents
  
  private val bound = new AxisAlignedBoundingBox(minExtents,maxExtents)
  
  private var models:Map[Any,Model] = Map()
  
  private var children:Map[OctNodeLoc,OctTree] = Map();
  private var parent:Option[OctTree] = None
  lazy val locationInParent:Option[OctNodeLoc] = findLocationInParent
  
  /**
   * Adds a model to the OctTree, recursively placing it in children 
   * trees until it won't fit at a lower depth, or is at the maximum depth
   * @param key a key to identify the Model
   * @param model the Model to put in the OctTree
   * @param maxLevels the maximum depth to place the object if it is small
   * enough to fit in progressively smaller child trees
   * @return reference to the final OctTree that the model is placed into
   */
  def putModel(key:Any,model:Model,maxLevels:Int):OctTree = {
	throw new UnsupportedOperationException("Not yet implemented.")
  }
  
  /**
   * Adds a model to the OctTree, recursively splitting it and placing the
   * sub-regions in child trees until the subdivided meshes contain fewer
   * triangles than a tree will allow.
   * @param key a key to identify the Model
   * @param model the Model to put in the OctTree
   * @param maxTriangles the maximum number of triangles to allow in an OctTree
   * before splitting the model into smaller pieces
   * @param minDist the minimum distance from a point on the model to the splitting
   * plane that will be used to consider whether the point is on the plane or not
   */
  def putModelAndSplit(key:Any,model:Model,maxTriangles:Int,minDist:Float = 0f):Unit = {
	if(model.mesh.faces <= maxTriangles){
	  models += (key -> model)
	}
	else{
      println("Found "+model.mesh.faces+" faces. Subdividing...")
	  var divModels:List[Option[Model]] = List(Some(model))
	  
	  //Generate a list of 8 sub-models, corresponding to the 
	  //8 child positions within this OctTree node
	  for(divPlane <- OctTree.divPlanes){
	 	var preDivModels = divModels
	    divModels = Nil
	    for(mod <- preDivModels){
	      val (neg,pos) = if(mod.isDefined){
	     	mod.get.split(new Plane3F(center,divPlane), minDist)
	      }
	      else{
	     	(None,None)
	      }
	      divModels = divModels ::: List(neg,pos)
	      val modCount1 = if(neg.isDefined) neg.get.mesh.faces else 0
	      val modCount2 = if(pos.isDefined) pos.get.mesh.faces else 0
	      println("...subdivided "+divPlane+" - "+modCount1+", "+modCount2)
	    }
	  }
      
	  //Create a list of (OctNodeLoc,Model) tuples, filtered 
	  //for the subdivided regions that contain Model data
	  val posAndModelList:List[(OctNodeLoc,Model)] = 
	 	  (OctTree.childPositions,divModels).zipped.map((pos,mod)=>(pos,mod)).
	 	  filter(_._2.isDefined).map((pAndM)=> (pAndM._1,pAndM._2.get))
	 
	  //Add each of the subdivided models to the appropriate child tree
	  //subdividing if necessary
      posAndModelList.foreach{(posAndMod) =>
        val (pos,mod) = posAndMod
	 	val child = getOrCreateChild(pos._1,pos._2,pos._3)
	 	child.putModelAndSplit(key, mod, maxTriangles, minDist)
	  }
	}
  }
  
  /**
   * Returns all models that were placed in this OctTree, and child
   * nodes of the tree as a map of key -> Seq[Model]
   * if OctTree or its children are within the specified bound's volume
   * @param within The bounding volume that represents the scene's viewable space. By
   * default, this is an infinite bound, which means no intersection test will be performed.
   * @return the models within the specified bound
   */
  def getModels(within:Bound = OctTree.noTestBound):Map[Any,Seq[Model]] = {
	var map:Map[Any,ArrayBuffer[Model]] = Map()
	
	getModels(within,map)
  }
  
  private def getModels(within:Bound, modelMap:Map[Any,ArrayBuffer[Model]]):Map[Any,ArrayBuffer[Model]] = {
	var map = modelMap
	var boundTest:Option[Bound] = None
	
	if(within.intersects(bound)){
	  boundTest = Some(within)
	}
	else if(within.contains(bound)){
	  boundTest = Some(OctTree.noTestBound)
	}
	
	//If we need to add this OctTree node's models and 
	//test for child node's models, then do that
	if(boundTest.isDefined){
	  for(keyMod <- models){
	    addModelsToMap((keyMod._1,Array(keyMod._2)))
	  }
	
	  for(posChild <- children){
	    val (pos,child) = posChild
	    map = child.getModels(boundTest.get,map)
	  }
	}
	
	def addModelsToMap(keyModel:(Any,Seq[Model])){
	  val buff:ArrayBuffer[Model] = map.get(keyModel._1).getOrElse{
	 	val newSeq = new ArrayBuffer[Model]()
	 	map += (keyModel._1 -> newSeq)
	 	newSeq
	  }
	  for(model <- keyModel._2){
	    buff+=(model)
	  }
	}
	map
  }
  
  /**
   * Get the child OctTree at the specified location, if it exists
   * @param location the (left-right,down-up,back-front) position of the child OctTree
   * @return
   */
  def child(location:OctNodeLoc):Option[OctTree] = {
	children.get(OctTree.getValidLocation(location))  
  }
  
  /**
   * Returns the child at the specified position, if it exists,
   * or creates a new empty child at the position, if it does not exist
   * @param location the (left-right,down-up,back-front) position of the child OctTree
   * @return the OctTree child in the specified position
   */
  def getOrCreateChild(location:OctNodeLoc):OctTree = {
	val goodLocation = OctTree.getValidLocation(location)
	val child = children.get(goodLocation)
	if(child.isDefined){
	  return child.get
	}
	else{
	  val (childMin:VectorF,childMax:VectorF) = goodLocation match{
	 	  case (Left,Down,Back) => (minExtents,center)
	 	  case (Left,Down,Front) => (VectorF(minExtents(0),minExtents(1),center(2)),VectorF(center(0),center(1),maxExtents(2)))
	 	  case (Left,Up,Back) => (VectorF(minExtents(0),center(1),minExtents(2)),VectorF(center(0),maxExtents(1),center(2)))
	 	  case (Left,Up,Front) => (VectorF(minExtents(0),center(1),center(2)),VectorF(center(0),maxExtents(1),maxExtents(2)))
	 	  case (Right,Down,Back) => (VectorF(center(0),minExtents(1),minExtents(2)),VectorF(maxExtents(0),center(1),center(2)))
	 	  case (Right,Down,Front) => (VectorF(center(0),minExtents(1),center(2)),VectorF(maxExtents(0),center(1),maxExtents(2)))
	 	  case (Right,Up,Back) =>  (VectorF(center(0),center(1),minExtents(2)),VectorF(maxExtents(0),maxExtents(1),center(2)))
	 	  case (Right,Up,Front) => (center,maxExtents)
	  }
	  val newChild = new OctTree(childMin,childMax)
	  newChild.parent = Some(this)
	  children += (goodLocation -> newChild)
	  return newChild
	}
  }
  
  /**
   * Get the left, right, down, up, back, or front sibling of this OctTree, if it exists
   * @param siblingPos
   * @return
   */
  def sibling(siblingPos:AxisPosition.AxisPosition):Option[OctTree] = {
	locationInParent.foreach{(loc) =>
	  val oppPos = OctTree.specifySide(siblingPos,loc)
	  if(OctTree.isOnSide(siblingPos,loc)){
	 	parent.get.sibling(siblingPos).foreach{(uncle) =>
	 	  return uncle.child(oppPos)
	 	}
	  }
	  else{
	 	return parent.get.child(oppPos)  
	  }
	}
	
	return None
  }
  
  private def findLocationInParent():Option[OctNodeLoc] = {
	for(par <- parent; child <- par.children){
	  val (key,tree) = child
	  if(tree eq this)
	 	return Some(key)
	}
	
	return None
  }

}

object OctTree{
  type OctNodeLoc = (AxisPosition.AxisPosition,AxisPosition.AxisPosition,AxisPosition.AxisPosition)

  val noTestBound = new InfiniteBound()
  
  private val divPlanes = List(
		  VectorF(1f,0f,0f),		//subdivide along the x, z, and then y axis
		  VectorF(0f,0f,1f),
		  VectorF(0f,1f,0f)) 
		  
  //By subdividing in the order of the div planes, we will get
  //the 9 child positions in this order
  private val childPositions = List(
		  (Left,Down,Back),(Left,Up,Back),
		  (Left,Down,Front),(Left,Up,Front),
		  (Right,Down,Back),(Right,Up,Back),
		  (Right,Down,Front),(Right,Up,Front)) 
		  
  private var posMap:Map[OctNodeLoc,OctNodeLoc] = Map()
  
  /**
   * Given an ordered tuple of 3 AxisLocations, return a valid
   * ordered version of the tuple in (x,y,z) order
   * @param unOrderedLoc the unordered position tuple
   * @return the (x,y,z) ordered tuple
   */
  private def getValidLocation(unOrderedLoc:OctNodeLoc):OctNodeLoc = {
	posMap.get(unOrderedLoc).getOrElse{
	  val loc = new Array[AxisPosition.AxisPosition](3)
	  
	  for(i <- 0 until 3){
	 	val axisPos = unOrderedLoc.productElement(i).asInstanceOf[AxisPosition.AxisPosition]
	 	loc(axisPos.id / 2) = axisPos
	  }
	   
	  require(loc.forall(_ != null),"OctTree location must specify X,Y, and Z axis locations")
	  
	  val orderedLoc = (loc(0),loc(1),loc(2)) 
	  posMap += (unOrderedLoc -> orderedLoc)
	  orderedLoc
	}
  }
  
  /**
   * Given an axis position, and an OctTree location, return a location
   * that is the same as the current location, except that the axis Position
   * is the one specified by the code calling this method
   * @param axisPos The position on the specified axis to change to 
   * @param nodeLoc The current location of the node
   * @return the new OctNode location
   */
  private def specifySide(axisPos:AxisPosition.AxisPosition,nodeLoc:OctNodeLoc):OctNodeLoc = {
	axisPos match{
		case Left => (axisPos,nodeLoc._2,nodeLoc._3)
		case Right => (axisPos,nodeLoc._2,nodeLoc._3)
		case Down => (nodeLoc._1,axisPos,nodeLoc._3)
		case Up => (nodeLoc._1,axisPos,nodeLoc._3)
		case Back => (nodeLoc._1,nodeLoc._2,axisPos)
		case Front => (nodeLoc._1,nodeLoc._2,axisPos)
	}
  }
  
  /**
   * Determine if the specified axis position is containd in the OctTree location
   * @param axisPos The position on the specified axis
   * @param nodeLoc The current location of the node
   * @return true if the position is in the location, or false otherwise
   */
  private def isOnSide(axisPos:AxisPosition.AxisPosition,nodeLoc:OctNodeLoc):Boolean = {
	nodeLoc.productIterator.exists(_ == axisPos)
  }
}
